package com.kevin.Code.Hash;

import java.lang.reflect.Array;
import java.util.*;

/**
 * @author Vinlee Xiao
 * @Classname GroupAnagrams
 * @Description Leetcode 49. 字母异位词分组 中等难度 参考题解
 * @Date 2021/10/23 19:50
 * @Version 1.0
 */
public class GroupAnagrams {

    List<List<String>> result = new ArrayList<>();

    /**
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams(String[] strs) {

        int len = strs.length;

        if (len == 0) {
            return result;
        }

        //用于保存已经存在分组中的坐标
        HashSet<Integer> indexHashSet = new HashSet<>();

        for (int i = 0; i < len; i++) {


            if (indexHashSet.contains(i)) {
                continue;
            }

            List<String> combine = new ArrayList<>();
            combine.add(strs[i]);
            char[] chars = strs[i].toCharArray();
            HashMap<Character, Integer> leftHashMap = new HashMap<>();

            for (int j = 0; j < chars.length; j++) {
                leftHashMap.put(chars[j], leftHashMap.getOrDefault(chars[j], 0) + 1);
            }

            for (int j = i + 1; j < len; j++) {

                if (indexHashSet.contains(j)) {
                    continue;
                }

                HashMap<Character, Integer> rightHashMap = new HashMap<>();
                char[] ch = strs[j].toCharArray();

                for (int k = 0; k < ch.length; k++) {

                    rightHashMap.put(ch[k], rightHashMap.getOrDefault(ch[k], 0) + 1);
                }

                if (check(leftHashMap, rightHashMap) && !indexHashSet.contains(j)) {
                    indexHashSet.add(j);
                    combine.add(strs[j]);
                }
            }

            if (combine.size() != 0) {
                result.add(new ArrayList<>(combine));
                combine.clear();
            }


        }


        return result;
    }

    /**
     * 暴力解法已经优化不少了
     *
     * @param t2
     * @param t1
     * @return
     */
    private boolean check(HashMap<Character, Integer> t1, HashMap<Character, Integer> t2) {

        if (t1.size() != t2.size()) {
            return false;
        }

        Set<Map.Entry<Character, Integer>> entries1 = t1.entrySet();

        for (Map.Entry<Character, Integer> entry : entries1) {
            Character key = entry.getKey();
            Integer value = entry.getValue();
            if (t2.getOrDefault(key, 0) != value) {

                return false;
            }
        }
        return true;
    }


    /**
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams1(String[] strs) {
        int len = strs.length;

        if (len == 0) {
            return new ArrayList<>();
        }

        HashMap<String, List<String>> hashMap = new HashMap<>();
        for (String str : strs) {


            char[] chars = str.toCharArray();
            Arrays.sort(chars);

            String key = new String(chars);

            List<String> subList = hashMap.getOrDefault(key, new ArrayList<String>());
            subList.add(str);
            hashMap.put(key, subList);

        }

        return new ArrayList<List<String>>(hashMap.values());

    }


    public static void main(String[] args) {
        GroupAnagrams groupAnagrams = new GroupAnagrams();
        String[] strs = new String[]{"a"};
        List<List<String>> lists = groupAnagrams.groupAnagrams(strs);

        for (List<String> list : lists) {

            for (String s : list) {
                System.out.print(s + "  ");

            }
            System.out.println();
        }
    }
}
